Loading [Contrib]/a11y/accessibility-menu.js
Index
Problem list
Graph
Chordal graph
References
TODO list
Graph
/
Chordal graph
(
Bibtex
)
P270
:
Enumeration of all chordal graphs in a graph
Input:
A graph $G$.
Output:
All chordal graphs in $G$.
Complexity:
$O(1)$ delay with $O(n^3)$ space.
Comment:
Using reverse search.
Reference:
[
Kiyomi2006
] (
Bibtex
)
P272
:
Enumeration of all chordal supergraph that contains a given graph
Input:
A graph $G = (V, E)$.
Output:
All chordal supergraphs each of which contain $G$.
Complexity:
$O(|V|^3)$ time for each and $O(|V|^2)$ space.
Comment:
Reference:
[
Kiyomi2006a
] (
Bibtex
)
P213
:
Enumeration of all chordal sandwiches in a graph
Input:
A graph $G = (V, E)$.
Output:
All chordal sandwiches in $G$.
Complexity:
Polynomial delay with polynomial space.
Comment:
Reference:
[
Kijima2010
] (
Bibtex
)
P509
:
Enumerate all maximal chordal induced graphs in a graph
Input:
A graph $G=(V, E)$.
Output:
All maximal chordal induced graphs in $G$.
Complexity:
$O(|E|^2|V|)$ delay.
Comment:
Exponential space. Proximity search.
Reference:
[
Conte2019
] (
Bibtex
)
P510
:
Enumerate all maximal connected chordal induced graphs in a graph
Input:
A graph $G=(V, E)$
Output:
All maximal connected chordal induced graphs in $G$.
Complexity:
$O(|E|^2|V|)$ delay.
Comment:
Exponential space. Proximity search.
Reference:
[
Conte2019
] (
Bibtex
)